#include <string.h>
#include <assert.h>

#include "vmalloc.h"
#include "vtl_vector.h"

typedef struct __vector {
    void *data;     /* 一个可变数组 */
    size_t size;    /* 已使用大小 */
    size_t alloc_size;  /* 已分配的内存大小 */
    size_t typesize;  /* 存储的类型大小 */
    vVectorOps *ops;
} vector_t;

typedef struct __vector_iterator {
    size_t index;
    vector_t *vector;
} *vector_iterator;

#define VECTOR_INIT_SIZE 16
#define VECTOR_INCR_FACTOR 2

static size_t __vector_offset(vector_t *v,size_t n)
{
    return n * v->typesize;
}


static void *__vector_off_ptr(vector_t *v, size_t off)
{
    return v->data + v->typesize * off;
}

static void __vector_realloc(vector_t *v, size_t new_count)
{
    v->data = vRealloc(v->data, __vector_offset(v, new_count));
    v->alloc_size = new_count;
}

static void __vector_free(vector_t *v, size_t start)
{
    size_t i = 0;
    for (i = start; i < v->size; i++) {
        void *ptr = *(void**)(__vector_off_ptr(v, i));
        if (v->ops && v->ops->vVectorFree)
            v->ops->vVectorFree(ptr);
        else
            vFree(ptr);
    }
}

static vector_iterator __alloc_iterator(vector_t *v, size_t index)
{
    vector_iterator iter = vMalloc(sizeof(*iter));
    iter->index = index;
    iter->vector = v;
    return iter;
}

vVector vVectorNew(size_t typesize,vVectorOps *ops)
{
    vector_t *v = vCalloc(1,sizeof(vector_t));
    assert(v);
    v->typesize = typesize;
    v->alloc_size = VECTOR_INIT_SIZE;
    v->ops = ops;
    v->data = vMalloc(__vector_offset(v,v->alloc_size));

    return (vVector)v;
}

/* 在pos处插入count个元素 */
static void __vector_insert(vector_t *v, size_t pos, const void *data, size_t count)
{
    if (v->size + count > v->alloc_size) {
        while (v->alloc_size < v->size + count)
            v->alloc_size *= VECTOR_INCR_FACTOR;
        __vector_realloc(v, v->alloc_size);
    }
    void *ptr = __vector_off_ptr(v, pos);
    size_t offset = __vector_offset(v, count);
    if (pos < v->size) {
        memmove(ptr + offset, ptr, __vector_offset(v, v->size - pos));
    }
    memcpy(ptr, data, offset);
    v->size += count;
}

static void __vector_erase(vector_t *v, size_t pos)
{
    if (pos >= v->size) return;
    void *ptr = __vector_off_ptr(v, pos);
    if (pos < v->size - 1) {
        /** 整体向前移动 */
        memmove(ptr, ptr + v->typesize, __vector_offset(v, v->size - 1 - pos));
    }
    v->size--;
}

void vVectorDelete(vVector vv)
{
    vector_t *v = (vector_t*)vv;
    assert(v);

    __vector_free(v,0);
    vFree(v->data);
    vFree(v);
}

/**
*@brief return vector[index]
*/
void *vVectorEntry(vVector vv, size_t index)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    if(index >= v->alloc_size)
        return NULL;
    return __vector_off_ptr(v,index);
}
/**
*@brief 访问第一个元素
*/
void *vVectorFront(vVector vv)
{
    return vVectorEntry(vv,0);
}
/**
*@brief 访问最后一个元素
*/
void *vVectorBack(vVector vv)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    return (v->size > 0) ? vVectorEntry(v,v->size - 1) : NULL;
}
/**
*@brief 返回指向第一个元素的迭代器
*/
vVectorIterator vVectorBegin(vVector vv)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    return __alloc_iterator(v,0);
}
/**
*@brief 返回指向最后一个元素的迭代器
*/
vVectorIterator vVectorEnd(vVector vv)
{
    vector_t *v = (vector_t*)vv;
    assert(v);
    return v->size > 0 ? __alloc_iterator(v,v->size - 1) : NULL;
}
/**
*@brief 返回指向下一个元素的迭代器，如果成功，则返回真
*/
bool vVectorNext(vVectorIterator iter)
{
    vector_iterator it = (vector_iterator )iter;
    assert(it);
    if(it->index + 1 == it->vector->size)
        return false;
    it->index++;
    return true;
}
/**
*@brief 返回指向上一个元素的迭代器，如果成功，则返回真
*/
bool vVectorPrev(vVectorIterator iter)
{
    vector_iterator it = (vector_iterator)iter;
    assert(it);
    if(it->index == 0)
        return false;
    it->index--;
    return true;
}
/**
*@brief取出迭代器中的数据
*/
void *vVectorGet(vVectorIterator iter)
{
    vector_iterator it = (vector_iterator)iter;
    assert(it);
    return __vector_off_ptr(it->vector,it->index);
}
/**
*@brief 释放一个迭代器
*/
void vVectorFreeIterator(vVectorIterator iter)
{
    vFree(iter);
}

void *vector_data(vector_t *v)
{
    assert(v);
    return v->data;
}

/**
*@brief 判断vector是否为空
*/
bool vVectorEmpty(vVector vv)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    return v->size == 0;
}

/**返回容纳的元素数 */
size_t vVectorSize(vVector vv)
{
    vector_t *v = (vector_t*)vv;
    assert(v);
    return v->size;
}

/**返回当前存储空间能够容纳的元素数 */
size_t vVectorCapacity(vVector vv)
{
    vector_t *v = (vector_t*)vv;
    assert(v);
    return v->alloc_size;
}

/**预留存储空间 */
void vVectorReserve(vVector vv, size_t new_cap)
{
    vector_t *v = (vector_t*)vv;
    assert(v);
    if(new_cap > v->alloc_size)
        __vector_realloc(v,new_cap);
}

/**改变vector中容纳元素的个数 */
void vVectorResize(vVector vv, size_t count)
{
    vector_t *v = (vector_t *)vv;
    assert(v);

    vVectorReserve(v, count);
    if (count < v->size) {
        __vector_free(v, count);
    } else {
        void *ptr = __vector_off_ptr(v, v->size);
        memset(ptr, 0, (count - v->size) * v->typesize);
    }
    v->size = count;
}

/**释放未使用的内存 */
void vector_shrink_to_fit(vVector vv)
{
    vector_t *v = (vector_t*)vv;
    assert(v);
    __vector_realloc(v,v->size);
}

/**在pos之前插入一个元素 */
void vVectorInsert(vVector vv, vVectorIterator pos, const void *data)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    vector_iterator it = (vector_iterator)pos;
    assert(it);
    if(it)
        __vector_insert(v,it->index,data,1);
}

/**在pos之前插入从data开始的count个元素 */
void vVectorInsert1(vVector vv, vVectorIterator pos, const void *data, size_t count)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    vector_iterator it = (vector_iterator)pos;
    assert(it);
    if(it)
        __vector_insert(v,it->index,data,count);
}

/**删除pos处的元素 */
void vVectorErase(vVector vv, vVectorIterator pos)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    vector_iterator it = (vector_iterator)pos;
    assert(it);
    __vector_erase(v,it->index);
}

/**在vector末尾添加一个元素
 * 假如要添加元素e，则需要vector_push_back(v, &e)(这里&必不可少)
 * 不管e是一个值还是一个指针，都需如此
 */
void vVectorPushBack(vVector vv, const void *data)
{
    vector_t *v = (vector_t *)vv;
    assert(v);

    __vector_insert(v,v->size,data,1);
}

/**从vector末尾弹出一个元素 */
void vVectorPopBack(vVector vv)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    if(v->size == 0)
        return ;
    v->size--;
}

/**交换两个元素 */
void vVectorSwap(vVector vv, size_t i, size_t j)
{
    vector_t *v = (vector_t *)vv;
    assert(v);

    if (i == j) return;
    char buf[v->typesize];
    void *vi = __vector_off_ptr(v, i);
    void *vj = __vector_off_ptr(v, j);
    memcpy(buf, vi, v->typesize);
    memcpy(vi, vj, v->typesize);
    memcpy(vj, buf, v->typesize);
}

/**清空vector */
void vVectorClear(vVector vv)
{
    vector_t *v = (vector_t *)vv;
    assert(v);
    __vector_free(v,0);
}
